package main.old.new_2023.last.month_8;


import main.dataStruct.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @Description: todo 1749. 任意子数组和的绝对值的最大值
 * 给你一个整数数组 nums 。一个子数组 [numsl, numsl+1, ..., numsr-1, numsr] 的 和的绝对值 为 abs(numsl + numsl+1 + ... + numsr-1 + numsr) 。
 * 请你找出 nums 中 和的绝对值 最大的任意子数组（可能为空），并返回该 最大值 。
 *
 * todo 剑指 Offer 55 - I. 二叉树的深度
 * 输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。
 *
 * todo 剑指 Offer 55 - II. 平衡二叉树
 * 输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。
 *
 * todo 剑指 Offer 42. 连续子数组的最大和
 * 输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
 * 要求时间复杂度为O(n)。
 *
 *
 * @Author: Take-off
 * @Date: 1:00 PM 2023/6/5
 * @Param:
 * @return:
 **/
public class Solution0808 {

    //连续子数组的最大和
    public int maxSubArray(int[] nums) {
        int count = nums[0];
        for (int i =1; i<nums.length ;i++){
            nums[i] =  nums[i] + Math.max(nums[i - 1], 0);
            count = Math.max(count, nums[i]);
        }
        return count;
    }

    public static void main(String[] args) {
        int[] temp = {-2,1,-3,4,-1,2,1,-5,4};

        Solution0808 test = new Solution0808();
        int i = test.maxSubArray(temp);
        System.out.println(i);
    }

    //平衡二叉树
    public boolean isBalanced(TreeNode root) {
        //广度优先，下一层应该是上一层的2倍，不是的话不允许再有下一层
        return recur(root) != -1;
    }

    public int recur(TreeNode root){
        if (root == null) return 0;
        int left = recur(root.left);
        if(left == -1) return -1;
        int right = recur(root.right);
        if(right == -1) return -1;
        return Math.abs(left - right) < 2 ? Math.max(left, right) + 1 : -1;
    }

    //二叉树的深度
    public int maxDepth(TreeNode root) {
        //广度优先，一层一层遍历
        int count  = 0;
        if (root == null){
            return count;
        }
        //两个数组交替插入，一个数组枚举完 +1
        Queue<TreeNode>  liuyi = new LinkedList<>();
        liuyi.add(root);
        Queue<TreeNode>  bobo = new LinkedList<>();
        while ( ! (liuyi.isEmpty() && bobo.isEmpty()) ){
            Queue<TreeNode>  temp = new LinkedList<>();
            if (bobo.isEmpty()){
                while (!liuyi.isEmpty()){
                    TreeNode poll = liuyi.poll();
                    if (poll.left != null){
                        temp.offer(poll.left);
                    }
                    if (poll.right != null){
                        temp.offer(poll.right);
                    }
                }
                bobo.addAll(temp);
            }else {
                while (!bobo.isEmpty()){
                    TreeNode poll = bobo.poll();
                    if (poll.left != null){
                        temp.offer(poll.left);
                    }
                    if (poll.right != null){
                        temp.offer(poll.right);
                    }
                }
                liuyi.addAll(temp);
            }
            count++;
        }
        return count;
    }

    //任意子数组和的绝对值的最大值
    public int maxAbsoluteSum(int[] nums) {
        //就是取最大值 或者 最小值
        int abs = 0;
        int max = 0;
        int min = 0;
        for (int temp: nums){
            max = Math.max(max,0) + temp;
            min = Math.min(min,0) + temp;
            abs = Math.max(abs,Math.max(max,-min));
        }
        return abs;
    }
}
